1. Field of the Invention
The field of the present invention pertains to performing mathematical operations. More particularly, the present invention relates to performing the modulus operation over a limited range.
2. Related Art
The modulus operator, represented in many programming languages as %, and sometimes called a remainder function, is used extensively in many applications. Some of these applications include video and audio compression techniques, e.g., the H.264 standard. Traditional methods of computation involving the modulus operator are relatively expensive, in terms of processor cycles and power consumption. For example, one common method of implementing the modulus operator is to continually loop subtraction operations until the remainder has been determined, which involves progressively more operations, as the dividend goes larger. For example, when calculating 4% 3, 3 is subtracted from 4 until a number between 0 and 2 remains, e.g., once. When calculating 17% 3, 3 is subtracted from 17 repeatedly until a number between 0 and 2 remains, e.g., five times, and that remainder is reported as the result of the modulus operation. Progressively larger dividend numbers results in progressively greater numbers of subtraction operations that must be performed.
Table 1, below, shows the modulus operator.
TABLE 1The Modulus Operatordividend mod divisor = remaindera % b = c
The modulus operator is used extensively in image and video processing, particularly in compression related applications. For example, given a macroblock number or pixel number, the horizontal and/or vertical coordinates of the macroblock or pixel can be determined. Another application, utilized in, e.g., the H.264 standard, is referencing a table of quantization values in the periodic manner. For example, the location of the table Lookup specified by the H.264 standard for a quantization parameter QP is “QP % 6.”
The traditional approach to the modulus operator are computationally very expensive, particularly in video applications. Performing dozens, or hundreds, of modulus operations on every frame of digital video data, with each modulus operation in that frame taking progressively greater computational time to resolve, means that video compression according to the specified standard require significant processing overhead.